package com.zk.algorithm;

/**
 * https://leetcode.com/problems/similar-string-groups/discuss/159425/Union-Find-Java-solution-based-on-mzchen's-solution
 */
public class SimilarStringGroups {

    public static void main(String...args) {
        System.out.println(new SimilarStringGroups().numOfSimilarStringGroups(new String[]{
                "tars","rats","arts","star"
        }));
    }

    public int numOfSimilarStringGroups(String[] groups) {
        UnionFind unionFind = new UnionFind(groups.length);

        // ["tars","rats","arts","star"]

        // -------------------------
        // tars
        //   i
        //         rats, arts, star
        //          j ---------->
        //
        // -------------------------
        // tars, rats,
        //         i
        //             arts, star
        //              j------>
        // -------------------------
        // tars, rats, arts,
        //               i
        //                   star
        //                     j
        // -------------------------
        for (int i = 0; i < groups.length - 1; i++) {
            for (int j = i + 1; j < groups.length; j++) {
                if (isSimilar(groups[i], groups[j])) {
                    unionFind.union(i, j);
                }
            }
        }

        return unionFind.size();
    }

    private boolean isSimilar(String a, String b) {
        int res = 0;
        int len = a.length();

        // tars
        // ||||
        // xVxV
        // ||||
        // rats

        for (int i=0; i<len; i++) {
            if (a.charAt(i) != b.charAt(i)) {
                // 如果某个字符串 X 能交换两个字母，就变为 Y 的话，那么就是相似
                // t a r s
                // ↑   ↑
                // r a t s
                if (++res > 2) {
                    return false;
                }
            }
        }

        return true;
    }

}
